﻿using System;
namespace QuickSilver.Help.Math.Algorithm
{
    /// <summary>
    /// 排序类算法类型集合
    /// </summary>
    public class Sort
    {
        /// <summary>
        /// 对整数数组利用快速排序方法进行排序（递归）
        /// </summary>
        /// <param name="SrcArray"></param>
        /// <param name="begin"></param>
        /// <param name="end"></param>
        /// <returns></returns>
        public static void QuickSort(ref int[] SrcArray, int begin, int end)
        {
            /*
             * 快速排序思想：通过一趟排序将要排序的数据分割成独立的两部分，
             * 其中一部分的所有数据都比另外一部分的所有数据都要小，
             * 然后再按此方法对这两部分数据分别进行快速排序，
             * 整个排序过程可以递归进行，以此达到整个数据变成有序序列。
             */
            if (begin < 0 || begin > end || end < 0)
                return;

            int left = begin, right = end, temp = SrcArray[left];

            while (left != right)
            {
                //数组的第一个元素被认定为基准元素，一趟排序后所有
                //小于第一个元素的元素都位于左边，其他都位于右边
                while (left < right && SrcArray[left] <= SrcArray[right])
                {
                    right--;
                }
                if (left < right)
                {
                    //发现有小于基准元素的元素，进行交换
                    //注意：进行交换后，基准元素被交换到右边，
                    //此时应该从左边开始搜索
                    temp = SrcArray[left];
                    SrcArray[left] = SrcArray[right];
                    SrcArray[right] = temp;
                }
                while (left < right && SrcArray[left] <= SrcArray[right])
                {
                    left++;
                }
                if (left < right)
                {
                    //发现有大于基准元素的元素，进行交换
                    //注意：进行交换后，基准元素被交换到右边，
                    //此时应该从左边开始搜索
                    temp = SrcArray[left];
                    SrcArray[left] = SrcArray[right];
                    SrcArray[right] = temp;
                }

            }
            QuickSort(ref SrcArray, right + 1, end);
            QuickSort(ref SrcArray, begin, right - 1);
        }

        /// <summary>
        /// 对数组利用快速排序方法进行排序（不使用递归思想的实现）
        /// </summary>
        /// <param name="SrcArray"></param>
        /// <param name="begin"></param>
        /// <param name="end"></param>
        /// <returns></returns>
        public static void QuickSortNonRecursion(int[] SrcArray, int begin, int end)
        {
            /*
             * 快速排序思想(非递归)：
             */
        }
    }

    /// <summary>
    /// 二叉树及其相关算法
    /// </summary>
    public class BinaryTree
    {
 
    }
}